package leetcode;

public class l0003_无重复字符的最长子串 {

    /**
     * 方式2
     */
    public static int lengthOfLongestSubstring2(String s) {
        if(s==null||s.length()==0){
            return 0;
        }
        char[] cs = s.toCharArray();

        int[] prevIdxes = new int[128];
        for (int i = 0; i < 128; i++) {
            prevIdxes[i] = -1;
        }
        // 收集答案
        int len = 0;
        // i-1位置结尾的情况下，往左推，推不动的位置是谁
        int i_1LeftMostIndex = -1;
        int curLen = 0;
        for (int i = 0; i < cs.length; i++) {
            // i位置结尾的情况下，往左推，推不动的位置是谁
            // i_1LeftMostIndex (i-1信息) -> i_1LeftMostIndex(i 结尾信息)
            i_1LeftMostIndex = Math.max(i_1LeftMostIndex, prevIdxes[cs[i]]);
            curLen = i - i_1LeftMostIndex;
            len = Math.max(len, curLen);
            prevIdxes[cs[i]] = i;
        }
        return len;
    }

    /**
     * 方式1
     */
    public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0){
            return 0;
        }
        char[] cs=s.toCharArray();
        int[] prevIdxes=new int[128];
        for(int i=0;i<prevIdxes.length;i++){
            prevIdxes[i]=-1;
        }
        prevIdxes[cs[0]]=0;
        int li=0;
        int max=1;
        for(int i=1;i<cs.length;i++){
            int pi=prevIdxes[cs[i]];
            prevIdxes[cs[i]]=i;
            if(li<=pi){
                li=pi+1;
            }

            max=Math.max(max,i-li+1);
        }
        return max;
    }


}
